//
// Created by vista on 2017/12/24.
//


#include <vector>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <set>
using namespace std;

#ifndef NULL
#define NULL 0
#endif

struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:

    void swap(ListNode* l1,int k){
        stack<int> stack1;
        ListNode * head = l1;
        for (int i = 0; i < k; ++i) {
            stack1.push(l1->val);
            l1 = l1->next;
        }
        for (int i = 0; i < k; ++i) {
            head->val = stack1.top();
            stack1.pop();
            head = head->next;
        }
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        if( head == NULL)
            return head;

        ListNode * ptr = head;
        do{
            ListNode * ptr0 = ptr;
            int count = 0;
            do{
                ptr = ptr->next;
                ++count;
            }while (ptr != NULL && count < k);
            if(count == k){
                swap(ptr0, k);
            }
        }while (ptr != NULL);

        return head;
    }
};

int main(){

    Solution solution;

    __uint64_t timebegin =  clock_gettime_nsec_np(CLOCK_REALTIME);

    ListNode * listNode = new ListNode(1);
    ListNode * head = listNode;
    for (int i = 0; i < 6; ++i) {
        ListNode * new_node = new ListNode(i+2);
        listNode->next = new_node;
        listNode = new_node;
    }

    ListNode * list = solution.reverseKGroup(head,1);

    while (list != NULL) {
        std::cout << list->val << ",";
        list = list->next;
    }
    cout << endl;

    __uint64_t timeend =  clock_gettime_nsec_np(CLOCK_REALTIME);

    cout << (timeend - timebegin) / 1000000.0 << endl;

    return 0;

}